A. Field of Invention
This invention relates to the area of data processing systems where a plurality of processors are competing for exclusive access to a portion of an addressable memory.
B. Status of the Prior Art
In data processing systems having multiple processors sharing a common addressable memory, a plurality of programs or processes are executed in parallel. This yields the advantage of increased throughput performance over machines where there is a single processor executing a single process.
Where there are multiple processes cooperating to perform a programmed function, a high level of coordination is necessary to ensure proper operation where resources are shared. One resource which may be shared in multi-processor data processing systems is addressable memory. It is well known in the art that machine language macro-instructions such as the biased-fetch, test-and-set, increment-and-test, or conditional-replace can be provided to accommodate the sharing of addressable memory. During execution of these instructions, the portion of memory upon which the operation is being performed is exclusively held, or "locked", by the processor executing the instruction; thus, they are referred to as "storage lock instructions". Should another processor attempt to execute a similar type of instruction on the same portion of memory while the first processor has that portion of memory locked, the second processor will be denied access to the storage location until the first processor has completed its exclusive use operation and has released the lock.
Each new generation of data processing systems has brought architectures having more and faster processors to drive the system. With respect to storage lock instructions, each generation has sought to keep the time required to coordinate lock processing to a minimum and maximize system performance.
The two basic approaches to storage lock operations are the "distributed" and "centralized" approaches. In the centralized approach to locking storage, the particular storage unit being locked contains the locking logic, and a lock granted signal must be provided to the processor requesting the lock to indicate that it has exclusive use of the requested storage location. In contrast, the distributed approach places the locking logic within each processor. Where each processor has the locking logic, a high level of coordination between the processors is necessary to ensure that a deadlock situation does not occur.
The distributed approach to processing storage lock instructions is shown in U.S. Pat. No. 4,984,153 issued Jan. 8, 1991 to Glen Kregness et al. for a "Storage Locking Control for a Plurality of Processors Which Share a Common Storage Unit" and assigned to Unisys Corporation, wherein each of the processors keeps a copy of each location in the shared storage which is locked by each of the processors. Special arbitration logic is provided to deal with the case where two processors request a lock simultaneously. This approach places the arbitration and locking logic at the processor level of the architecture, and results in lock processing overhead for the processor which is directly proportional to the number of processors in the system. Furthermore, with the point-to-point communications shown, the space required for inter-processor cabling drastically increases as each additional processor requires cables between the it and each processor already in the system.
The "Lock Control for a Shared Storage in a Data Processing System" described in U.S. Pat. No. 4,733,352, issued Mar. 22, 1988 to Kouji Nakamura et al., shows a plurality of processors sharing a main storage through a plurality of storage controllers. Each storage controller is coupled to a main storage unit and processes the main storage requests for each of the coupled processors. While the described locking mechanism removes the locking logic from the processors and thereby reduces the cabling between the processors, its locking mechanism has each locking unit maintaining a copy of lock information stored in the other locking unit. When the lock information is duplicated in the lock units, extra logic hardware is required to synchronize the lock operation between each of the lock units.
The "Shared Resource Locking Apparatus" described by Starr in the International Patent Application published under the Patent Cooperation Treaty, International Pub. No. WO 83/04117, has a hardware lock unit for limiting concurrent use of shared memory in a data processing system with a bus architecture. The publication shows that where the lock unit is centralized with respect to the resource being locked, logic for coordinating between lock units is unnecessary. When a processor wishes to lock a selected portion of addressable memory, it sends its processor identification, a read command, and an address indicating the memory portion to be locked over the system bus to the shared memory unit. The shared memory unit then checks whether the memory portion indicated is already locked by another processor. If so, the lock request is held and the read from memory is not performed. The requesting processor must await its turn to lock the indicated portion of memory, and the shared memory unit waits until the lock is granted to perform the read operation. Each portion of the shared memory that is to be treated as a separate lockable resource has a lock register. The lock register contains an identifier for the requestor currently having the resource locked, and a bit map field indicating which processors have lock requests outstanding for the resource.
The above-referenced patents do not disclose the system of the present invention for locking a portion of addressable memory. The system set forth reduces the locking logic by centralizing the locking control, minimizes the point-to-point cabling necessary for multiple processors, performs the lock control and memory read operations in parallel, and detects when processors become inoperative to avoid deadlock. These and other advantages are described in more detail in the following discussion.